{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Delete and Earn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: deleteAndEarn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除并获得点数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，你可以对它进行一些操作。</p>\n",
    "\n",
    "<p>每次操作中，选择任意一个 <code>nums[i]</code> ，删除它并获得 <code>nums[i]</code> 的点数。之后，你必须删除 <strong>所有 </strong>等于 <code>nums[i] - 1</code> 和 <code>nums[i] + 1</code> 的元素。</p>\n",
    "\n",
    "<p>开始你拥有 <code>0</code> 个点数。返回你能通过这些操作获得的最大点数。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,4,2]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>\n",
    "删除 4 获得 4 个点数，因此 3 也被删除。\n",
    "之后，删除 2 获得 2 个点数。总共获得 6 个点数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,2,3,3,3,4]\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>\n",
    "删除 3 获得 3 个点数，接着要删除两个 2 和 4 。\n",
    "之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。\n",
    "总共获得 9 个点数。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 <= nums[i] <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [delete-and-earn](https://leetcode.cn/problems/delete-and-earn/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [delete-and-earn](https://leetcode.cn/problems/delete-and-earn/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,4,2]', '[2,2,3,3,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        buffer = dict()\n",
    "        max_num = 0\n",
    "        for num in nums:\n",
    "            if max_num < num:\n",
    "                max_num = num\n",
    "            if num in buffer.keys():\n",
    "                buffer[num] += 1\n",
    "            else:\n",
    "                buffer[num] = 1\n",
    "        \n",
    "        single_nums = [int(i) for i in buffer.keys()]\n",
    "        single_nums.sort()\n",
    "        l = len(single_nums)\n",
    "        \n",
    "        dp = [0 for _ in range(l+1)]\n",
    "        dp[1] = single_nums[0]*buffer[single_nums[0]]\n",
    "        last = single_nums[0]\n",
    "        for i in range(1, len(single_nums)):\n",
    "            if last == single_nums[i]-1:\n",
    "                dp[i+1] = max(dp[i-1]+single_nums[i]*buffer[single_nums[i]], dp[i])\n",
    "            else:\n",
    "                dp[i+1] = dp[i] + single_nums[i]*buffer[single_nums[i]]\n",
    "            last = single_nums[i]\n",
    "        return dp[-1]\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return 0\n",
    "        d = {}\n",
    "        for n in nums:\n",
    "            d[n] = d.get(n, 0) + 1\n",
    "        keys = sorted(d.keys())\n",
    "        dp = [0] * len(keys)\n",
    "        dp[0] = keys[0] * d[keys[0]]\n",
    "        for i in range(1, len(dp)):\n",
    "            v = keys[i] * d[keys[i]]\n",
    "            if keys[i] != keys[i-1] + 1:\n",
    "                dp[i] = dp[i-1] + v\n",
    "            else:\n",
    "                if i == 1:\n",
    "                    dp[i] = max(v, dp[0])\n",
    "                else:\n",
    "                    dp[i] = max(v + dp[i-2], dp[i-1])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        dp = [0 for _ in range(10001)]\n",
    "        c = collections.Counter(nums)\n",
    "        ret = float(\"-inf\")\n",
    "        dp[1] = c[1] if 1 in c else 0\n",
    "        for i in range(2,10001):\n",
    "            if i in c:\n",
    "                dp[i] = max(dp[i-1],dp[i-2]+c[i]*i)\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "        return dp[-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cnt = [0]*10001\n",
    "        res = [0]*10001\n",
    "        for num in nums:\n",
    "            cnt[num]+=1\n",
    "        res[1] = cnt[1]\n",
    "        for i in range(2, 10001):\n",
    "            res[i] = max(i*cnt[i]+res[i-2], res[i-1])\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cc = {}\n",
    "        ns = set()\n",
    "        for n in nums:\n",
    "            if n in cc:\n",
    "                cc[n] += 1\n",
    "            else:\n",
    "                cc[n] = 1\n",
    "                ns.add(n)\n",
    "            \n",
    "        ns = sorted(list(ns))\n",
    "        \n",
    "        cals = {}\n",
    "        def dynamic(i):\n",
    "            if i >= len(ns):\n",
    "                return 0\n",
    "            if i in cals:\n",
    "                return cals[i]\n",
    "            ans = 0\n",
    "            if i+1 < len(ns) and ns[i+1] == ns[i]+1:\n",
    "                ans = max(ans, ns[i]*cc[ns[i]]+dynamic(i+2))\n",
    "                ans = max(ans, dynamic(i+1))\n",
    "            else:\n",
    "                ans = max(ans, ns[i]*cc[ns[i]]+dynamic(i+1))\n",
    "            cals[i] = ans\n",
    "            return ans\n",
    "        return dynamic(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        import collections\n",
    "        if len(nums) == 0:\n",
    "           return 0\n",
    "        count = collections.Counter(nums)\n",
    "        mr = [0] * (max(nums)+1)\n",
    "        mr[1] = count[1]\n",
    "        for i in range(2 , max(nums)+1):\n",
    "            mr[i] = max(count[i]*i + mr[i-2] , mr[i-1])\n",
    "        return mr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        if not nums:return 0\n",
    "        nums=sorted(nums)\n",
    "        a=[[nums[0],1]]\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]!=a[-1][0]:a.append([nums[i],1])\n",
    "            else:a[-1][1]+=1\n",
    "        dp=[0]*len(a)\n",
    "        dp[0]=a[0][0]*a[0][1]\n",
    "        if len(a)==1:return dp[0]\n",
    "        #if a[1]!=\n",
    "        for i in range(1,len(a)):\n",
    "            dp[i]=a[i][0]*a[i][1]\n",
    "            for j in range(i):\n",
    "                if a[j][0]!=a[i][0]-1:dp[i]=max(dp[i],a[i][0]*a[i][1]+dp[j])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        if not nums: \n",
    "            return 0\n",
    "        count = collections.Counter(nums)\n",
    "        arr = sorted(k for k in count.keys())\n",
    "        n = len(arr)\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = arr[0] * count[arr[0]]\n",
    "        for i in range(1, n):\n",
    "            if arr[i] == arr[i - 1] + 1:\n",
    "                dp[i] = max(dp[i - 1], dp[i - 2] + arr[i] * count[arr[i]])\n",
    "            else:\n",
    "                dp[i] = dp[i - 1] + arr[i] * count[arr[i]]\n",
    "                \n",
    "        return dp[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        lst=[0 for i in range(max(nums)+1)]\n",
    "        for item in nums:\n",
    "            lst[item]+=1\n",
    "        dp=[0 for _ in range(len(lst))]\n",
    "        dp[1]=lst[1]\n",
    "        for i in range(2,len(dp)):\n",
    "            dp[i]=max(dp[i-1],dp[i-2]+lst[i]*i)\n",
    "        \n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        cnt = [0]*(1+max(nums))\n",
    "\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        \n",
    "        a,b=0,0\n",
    "        for i in range(1, len(cnt)):\n",
    "            c = max(a + cnt[i]*i, b)\n",
    "            a, b = b, c\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        def my_rob(nums: List[int]) -> int:\n",
    "            n = len(nums)\n",
    "\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            elif n == 1:\n",
    "                return nums[0]\n",
    "            elif n == 2:\n",
    "                return max(nums[0], nums[1])\n",
    "\n",
    "            # 状态定义：上上个最大偷取金额状态，上个最大偷取金额状态\n",
    "            pre, cur = nums[0], max(nums[0], nums[1])\n",
    "            # 状态转移方程\n",
    "            for i in range(2, n):\n",
    "                pre, cur = cur, max(cur, pre + nums[i])\n",
    "            # 输出\n",
    "            return cur\n",
    "\n",
    "        if not nums: return 0\n",
    "        \n",
    "        n = max(nums)\n",
    "        earns = [0] * (n+1)\n",
    "\n",
    "        for num in nums:\n",
    "            earns[num] += num\n",
    "        \n",
    "        return my_rob(earns)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        count = [0] * (max(nums) + 1)\n",
    "        for num in nums:\n",
    "            count[num] += num\n",
    "        m = len(count)\n",
    "        dp = [0] * m\n",
    "        dp[0], dp[1] = 0 , count[1]\n",
    "        for i in range(2,m):\n",
    "            dp[i] = max(dp[i-1], dp[i-2] + count[i])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        total = 0\n",
    "        counts = {}\n",
    "        for num in nums:\n",
    "            counts[num] = counts.get(num, 0) + 1\n",
    "        for num in counts:\n",
    "            if num + 1 not in counts and num - 1 not in counts:\n",
    "                total += num * counts[num]\n",
    "                counts[num] = 0\n",
    "        arr = []\n",
    "        for num in counts:\n",
    "            if counts[num] != 0:\n",
    "                arr.append(num)\n",
    "        arr.sort()\n",
    "        print(arr, counts)\n",
    "        table = {}\n",
    "        result = self.cal(arr, counts, 0, table)\n",
    "        return result + total\n",
    "\n",
    "    def cal(self, arr, counts, i, table):\n",
    "        if i in table:\n",
    "            return table[i]\n",
    "        n = len(arr)\n",
    "        if i >= n:\n",
    "            return 0\n",
    "        d, nd = 0, 0\n",
    "        # delete the number\n",
    "        if i == n - 1:\n",
    "            d = counts[arr[i]] * arr[i]\n",
    "        else:\n",
    "            if arr[i + 1] == arr[i] + 1:\n",
    "                d = self.cal(arr, counts, i + 2, table) + counts[arr[i]] * arr[i]\n",
    "            else:\n",
    "                d = self.cal(arr, counts, i + 1, table) + counts[arr[i]] * arr[i]\n",
    "        # not delete the number\n",
    "        if i == n - 1:\n",
    "            # must delete\n",
    "            nd = 0\n",
    "        else:\n",
    "            if arr[i + 1] == arr[i] + 1:\n",
    "                # delete the next number\n",
    "                if i + 2 < n:\n",
    "                    if arr[i + 2] == arr[i + 1] + 1:\n",
    "                        nd = self.cal(arr, counts, i + 3, table) + counts[arr[i + 1]] * arr[i + 1]\n",
    "                    else:\n",
    "                        nd = self.cal(arr, counts, i + 2, table) + counts[arr[i + 1]] * arr[i + 1]\n",
    "                else:\n",
    "                    nd = counts[arr[i + 1]] * arr[i + 1]\n",
    "            else:\n",
    "                # must delete\n",
    "                nd = 0\n",
    "        table[i] = max(d, nd)\n",
    "        return table[i]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        c = collections.Counter(nums)\n",
    "        dp = collections.defaultdict(int)\n",
    "        \n",
    "        # print(l)\n",
    "        print(c)\n",
    "        for i in range(10001):\n",
    "            dp[i] = max(dp[i-1] if i -1 >= 0 else 0,(dp[i-2] if i -2 >= 0 else 0) + (c[i]*i if i in c else 0))\n",
    "            \n",
    "        # print('here')\n",
    "        return dp[10000]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        if nums==[]:\n",
    "            return 0\n",
    "        val = [0]*10001\n",
    "        for i in range(len(nums)):\n",
    "            val[nums[i]]+=nums[i]\n",
    "        f = [[0,0] for i in range(10001)]\n",
    "        f[min(nums)][1] = val[min(nums)] \n",
    "        for i in range(min(nums)+1,max(nums)+1):\n",
    "            f[i][0] = max(f[i-1][0],f[i-1][1])\n",
    "            f[i][1] = max(f[i-1][0],f[i-2][0],f[i-2][1])+val[i]\n",
    "        return max(f[max(nums)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        new = [0] * 10001\n",
    "        for num in nums:\n",
    "            new[num] += num\n",
    "\n",
    "        first, second = new[0], new[1]\n",
    "        for i in range(2, 10001):\n",
    "            first, second = second, max(first+new[i], second)\n",
    "        return second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        counter = Counter(nums)\n",
    "        min_num = min(nums)\n",
    "        n_len = max(nums) - min_num + 1\n",
    "        dp = [0 for _ in range(n_len + 1)]\n",
    "        dp[1] = min_num * counter.get(min_num)\n",
    "        for i in range(2, n_len + 1):\n",
    "            now_num = min_num + i - 1\n",
    "            dp[i] = max(dp[i - 1], dp[i - 2] + now_num * counter.get(now_num, 0))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 2:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            sum_li = [0] * (max(nums) + 1)\n",
    "            dit = {}\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] not in dit.keys():\n",
    "                    sum_li[nums[i]] = nums[i] * nums.count(nums[i])\n",
    "                    dit[nums[i]] = i\n",
    "            # print(dit)\n",
    "            # print(sum_li)\n",
    "            dp = [0] * (max(nums) + 1)\n",
    "            dp[1], dp[2] = sum_li[1], sum_li[2]\n",
    "            for i in range(3, len(sum_li)):\n",
    "                dp[i] = max(dp[i-2], dp[i-3]) + sum_li[i]\n",
    "            # print(dp)\n",
    "            return max(dp)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "def cmp(x, y):\n",
    "    return -1 if x<y else 1 if x>y else 0\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        def dp(nums: List[int]):\n",
    "            n = len(nums);\n",
    "\n",
    "            if n==1:\n",
    "                return nums[0];\n",
    "            if n==2:\n",
    "                return max(nums[0], nums[1])\n",
    "\n",
    "            pre=nums[0];\n",
    "            cur=max(nums[0], nums[1]);\n",
    "            for i in range(2,n):\n",
    "                nex = max(pre+nums[i], cur);\n",
    "                pre = cur;\n",
    "                cur = nex;\n",
    "            return cur\n",
    "\n",
    "        nums = sorted(nums, key=cmp_to_key(cmp))\n",
    "\n",
    "        prev = nums[0]\n",
    "\n",
    "        sums=[[nums[0]]];\n",
    "        \n",
    "        for num in nums[1:]:\n",
    "            if num == prev+1:\n",
    "                sums[-1].append(num);\n",
    "                prev=num;\n",
    "\n",
    "            elif num == prev:\n",
    "                sums[-1][-1]+=num;\n",
    "\n",
    "            else:\n",
    "                sums.append([num]);\n",
    "                prev=num;\n",
    "\n",
    "        \n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for isum in sums:\n",
    "            ans += dp(isum)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob1(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a, b = 0, 0\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > 0:\n",
    "                a, b = max(a, b), max(a + i * nums[i], b)\n",
    "            else:\n",
    "                a, b = max(a, b), 0\n",
    "        return b\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        mx = max(nums)\n",
    "        cnt = [0] * (mx + 1)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        return self.rob1(cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        pp = 0\n",
    "        p = 0\n",
    "\n",
    "        i = 0\n",
    "        j = 1\n",
    "        while i < len(nums):\n",
    "            while j < len(nums) and nums[j] == nums[i]:\n",
    "                j += 1\n",
    "\n",
    "            if nums[i] == nums[i-1] + 1:\n",
    "                ans = max(p, pp + (j-i)*nums[i])\n",
    "            else:\n",
    "                ans = p + (j-i)*nums[i]\n",
    "\n",
    "            pp = p\n",
    "            p = ans\n",
    "            i = j\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dp(self,nums:list[int])->int:\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return nums[0]\n",
    "        first,second=nums[0],max(nums[0],nums[1])\n",
    "        for i in range(2,n):\n",
    "            temp=max(second,first+nums[i])\n",
    "            first,second=second,temp\n",
    "        return second\n",
    "\n",
    "    def deleteAndEarn(self,nums:list[int])->int:\n",
    "        n,ans=len(nums),0\n",
    "        nums.sort()\n",
    "        s=[nums[0]]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            val=nums[i]\n",
    "            if nums[i]==nums[i-1]:\n",
    "                s[len(s) - 1]+=nums[i]\n",
    "            elif nums[i]==nums[i-1]+1:\n",
    "                s.append(nums[i])\n",
    "            else:\n",
    "                ans+=self.dp(s)\n",
    "                s=[val]\n",
    "\n",
    "        ans+=self.dp(s)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        fre = [0] * (max(nums) + 1)\n",
    "        dp = [0] * len(fre)\n",
    "\n",
    "        for n in nums:\n",
    "            fre[n] += 1\n",
    "\n",
    "        dp[1] = fre[1]\n",
    "        for i in range(2, len(fre)):\n",
    "            dp[i] = max(dp[i-1], dp[i-2] + i*fre[i])\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        # 根据数组最大值为长度创建数组，长度比最大值多1\n",
    "        # 统计重复值(因为有重复的值时, 删除操作只有一次)\n",
    "        # 也相当于把它们按序排列了, 以之前数组的每项值作为索引\n",
    "        sumArr = [0] * (max(nums)+1)\n",
    "        \n",
    "        for val in nums:\n",
    "            sumArr[val] += val\n",
    "        \n",
    "        size = len(sumArr)\n",
    "        # 只有一个的时候\n",
    "        if size < 2:\n",
    "            return sumArr[0]\n",
    "\n",
    "        first, second = sumArr[0], max(sumArr[0], sumArr[1])\n",
    "        for i in range(2, size):\n",
    "            first, second = second, max(second, first+sumArr[i])\n",
    "        \n",
    "        return second\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "\n",
    "        my_dict = {}\n",
    "\n",
    "        for i in nums:\n",
    "            my_dict[i] = my_dict.get(i, 0) + 1\n",
    "\n",
    "        nums = sorted(my_dict.keys())\n",
    "\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0] * my_dict[nums[0]]\n",
    "\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0] * my_dict[nums[0]]\n",
    "\n",
    "        if nums[1] - nums[0] == 1:\n",
    "            dp[1] = max(dp[0], nums[1] * my_dict[nums[1]])\n",
    "        else:\n",
    "            dp[1] = dp[0] + nums[1] * my_dict[nums[1]]\n",
    "            \n",
    "        for i in range(2,n):\n",
    "            if nums[i] - nums[i-1] == 1:\n",
    "                dp[i] = max(dp[i-1], dp[i-2] + nums[i] * my_dict[nums[i]])\n",
    "            else:\n",
    "                dp[i] = dp[i-1] + nums[i] * my_dict[nums[i]]\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        inspire = [0]*max(nums)+[0]\n",
    "        for i in nums:\n",
    "            inspire[i] += 1\n",
    "        x0, x1 = 0, inspire[1]\n",
    "        for i, v in enumerate(inspire[2:],2):\n",
    "            x0, x1 = x1, max(x1, x0+i*v)\n",
    "        return x1\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "        # c = Counter(nums)\n",
    "        # ckey = sorted(c.keys())\n",
    "        # if len(ckey) == 1:\n",
    "        #     return ckey[0]*c[ckey[0]]\n",
    "        # x0 = ckey[0]*c[ckey[0]]\n",
    "        # x1 = ckey[1]*c[ckey[1]]+x0 if x1>1+x0 else max(ckey[1]*c[ckey[1]], x0)\n",
    "        # for j in range(2, len(ckey)):\n",
    "        #     if ckey[j] > 1+ckey[j-1]:\n",
    "        #         x0, x1 = x1, x1+ckey[1]*c[ckey[1]]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        maxval=max(nums)\n",
    "        ct=[0]*(maxval+1)\n",
    "        f=[0]*(maxval+1)\n",
    "        for i in nums:\n",
    "            ct[i]+=1\n",
    "        for i in range(1,(maxval+1)):\n",
    "            if i==1:\n",
    "                f[i]=i*ct[i]\n",
    "            elif i==2:\n",
    "                f[i]=max(f[i-1],i*ct[i])\n",
    "            else:\n",
    "                f[i]=max(f[i-1],i*ct[i]+f[i-2])\n",
    "        return f[maxval]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        sums = [0] * (10000+1)\n",
    "        maxVal = 0\n",
    "        for value in nums:\n",
    "            sums[value] += value\n",
    "            maxVal = max(value, maxVal)\n",
    "        NoTake = 0\n",
    "        TryTake = sums[1]\n",
    "        for i in range(2, maxVal + 1):\n",
    "            NoTake, TryTake = TryTake, max(TryTake, NoTake+sums[i])\n",
    "        # print(NoTake, Take)\n",
    "        return TryTake"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.value_count = defaultdict(int)\n",
    "        self.sorted_key = []\n",
    "        self.value_for_each_key = []\n",
    "\n",
    "\n",
    "    # 排序，从小到大删除。\n",
    "    # n-2 被删除的条件下已获得最大点数 + 删除n 能获得的点数 vs\n",
    "    # n-1 被删除的条件下已获得最大点数, 则当前n 也会被删除\n",
    "\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        for n in nums:\n",
    "            self.value_count[n] += 1\n",
    "\n",
    "        self.sorted_key = sorted(self.value_count.keys())\n",
    "        length = len(self.sorted_key)\n",
    "\n",
    "        self.value_for_each_key = [0] * length\n",
    "\n",
    "        if length == 1:\n",
    "            return self.sorted_key[0] * self.value_count[self.sorted_key[0]]\n",
    "\n",
    "        for i in range(length):\n",
    "            current_value = self.sorted_key[i]\n",
    "            current_total_point = current_value * self.value_count[current_value]\n",
    "            if i == 0:\n",
    "                self.value_for_each_key[i] = current_total_point\n",
    "                continue\n",
    "\n",
    "            if self.sorted_key[i-1] + 1 != current_value:\n",
    "                self.value_for_each_key[i] = self.value_for_each_key[i-1] + current_total_point\n",
    "            else:\n",
    "                if i == 1:\n",
    "                    self.value_for_each_key[i] = max(\n",
    "                        self.value_for_each_key[i-1],\n",
    "                        current_total_point\n",
    "                    )\n",
    "                else:\n",
    "                    self.value_for_each_key[i] = max(\n",
    "                        self.value_for_each_key[i-1],\n",
    "                        self.value_for_each_key[i-2] + current_total_point\n",
    "                    )\n",
    "\n",
    "        return self.value_for_each_key[length-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        def rob_dp(nums: list[int]) -> int:\n",
    "            n = len(nums)\n",
    "            if n == 1:\n",
    "                return nums[0]\n",
    "            dp = [0 for _ in range(n)]\n",
    "            dp[0] = nums[0]\n",
    "            dp[1] = max(nums[0], nums[1])\n",
    "            for i in range(2, n):\n",
    "                dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])\n",
    "            return dp[n - 1]\n",
    "        compress = [0 for _ in range(max(nums) + 1)]\n",
    "        for num in nums:\n",
    "            compress[num] += num\n",
    "        return rob_dp(compress)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        #dp[n] = max(dp[n-1],dp[n-2]+nums[n])\n",
    "        #必须删除所有等于nums[i]-1元素:\n",
    "        #dp[n] = max(dp[n-1],dp[n-2]+nums[n])?\n",
    "        dnums = {}\n",
    "        maxn = 0\n",
    "        minn = 10000\n",
    "        for i in nums:\n",
    "            if(i < minn):\n",
    "                minn = i\n",
    "            if(i > maxn):\n",
    "                maxn = i\n",
    "            if(i in dnums):\n",
    "                dnums[i] += i\n",
    "            else:\n",
    "                dnums[i] = i\n",
    "        print(dnums)\n",
    "        dp = [dnums[minn]]\n",
    "        if(minn+1 in dnums):\n",
    "            dp.append(max(dp[0],dnums[minn+1]))\n",
    "        else:\n",
    "            dp.append(dnums[minn])\n",
    "        for i in range(2,maxn-minn+1):\n",
    "            if(i+minn in dnums):\n",
    "                dpi = max(dp[i-1],dp[i-2]+dnums[i+minn])\n",
    "            else:\n",
    "                dpi = max(dp[i-1],dp[i-2])\n",
    "            dp.append(dpi)\n",
    "        print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        #n = len(nums)-1\n",
    "        '''\n",
    "        if n==0:\n",
    "            return nums[0]\n",
    "        if n==1:\n",
    "            return nums[0]+nums[1]\n",
    "        num = sorted(nums)\n",
    "        sum={}\n",
    "        for i in num:\n",
    "            if str(i) in sum.keys():\n",
    "                sum[str(i)]+=1\n",
    "            else:\n",
    "                sum[str(i)]=1\n",
    "        num = list(sum.keys())\n",
    "        n = len(num)-1\n",
    "        a,b,c=0,0,int(num[0])*sum[num[0]]\n",
    "        for i in range(1,n+1):\n",
    "            if int(num[i])-int(num[i-1])!=1:\n",
    "                a,b,c=b,c,max(b+int(num[i])*sum[num[i]],c+int(num[i])*sum[num[i]])\n",
    "            elif int(num[i])-int(num[i-1])==1:\n",
    "                a,b,c=b,c,max(c,b+int(num[i])*sum[num[i]],a+int(num[i])*sum[num[i]])\n",
    "        return c\n",
    "        '''\n",
    "        sums={}\n",
    "        for i in nums:\n",
    "            if i in sums.keys():\n",
    "                sums[i]+=i\n",
    "            else:\n",
    "                sums[i]=i\n",
    "        n = len(sums)-1\n",
    "        if n==0:\n",
    "            return sums[nums[0]]\n",
    "        nums=list(set(nums))\n",
    "        if nums[1]-nums[0]==1:\n",
    "            a,b=sums[nums[0]],max(sums[nums[1]],sums[nums[0]])\n",
    "        else:\n",
    "            a,b=sums[nums[0]],sums[nums[1]]+sums[nums[0]]\n",
    "        for i in range(2,n+1):\n",
    "            if (nums[i]-1)!=nums[i-1]:\n",
    "                a,b=b,b+sums[nums[i]]\n",
    "            if (nums[i]-1)==nums[i-1]:\n",
    "                a,b=b,max(b,a+sums[nums[i]])\n",
    "        return b\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        #3转换为打家劫舍问题\n",
    "        max_val=max(nums)\n",
    "        total=[0]*(max_val+1)\n",
    "        for i in nums:total[i]+=i\n",
    "\n",
    "        \"\"\"\n",
    "        ##为什么用之前的打家劫舍的方式写，会出错\n",
    "        \"\"\"\n",
    "        # def rob(nums):\n",
    "        #     dp=[[0,0]for i in range(len(nums))]\n",
    "        #     dp[0][0]=0#不偷第一件\n",
    "        #     dp[0][1]=nums[0]#偷第一家\n",
    "        #     for i in range(1,len(nums)):\n",
    "        #         dp[i][0]=max(dp[i-1][0],dp[i-1][1])\n",
    "        #         dp[i][1]=dp[i-1][0]+nums[i]\n",
    "        #     return max(dp[len(nums)-1])\n",
    "        # return rob(nums)\n",
    "        n=len(nums)\n",
    "        if n==1:return nums[0]\n",
    "        dict={}#记录元素对应的个数\n",
    "        for num in nums:dict[num]=dict.get(num,0)+1\n",
    "        nums=list(set(nums))\n",
    "        nums=[0]+nums#前面补了一个0\n",
    "        nums.sort()\n",
    "        dp={0:0,1:nums[1]*dict[nums[1]]}#dp也可以用字典来写\n",
    "        size=len(nums)\n",
    "        for i in range(2,size):\n",
    "            if nums[i]==nums[i-1]+1:\n",
    "                dp[i]=max(dp[i-1],dp[i-2]+nums[i]*dict[nums[i]])\n",
    "            elif nums[i]>nums[i-1]+1:\n",
    "                dp[i]=dp[i-1]+nums[i]*dict[nums[i]]\n",
    "        return dp[size-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        cnt = [0] * 100000 \n",
    "        m = 0 \n",
    "        for i in nums:\n",
    "            cnt[i] += 1\n",
    "            m = max(i,m)\n",
    "        \n",
    "        f= [[0]* 2 for _ in range(m+1)]\n",
    "        for j in range(1,len(f)):\n",
    "            f[j][1] = f[j-1][0] + cnt[j] * j \n",
    "            f[j][0] = max(f[j-1][0], f[j-1][1])\n",
    "        return max(f[-1][0], f[-1][1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteAndEarn(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        dp = [[0]*2 for _ in range(n)]\n",
    "        countDp = 0\n",
    "        count=0\n",
    "        while(count+1<n and nums[count+1]==nums[count]):\n",
    "            count += 1\n",
    "        dp[countDp][0] = 0\n",
    "        dp[countDp][1] = nums[0]*(count+1)\n",
    "        countDp = countDp+1\n",
    "        print(\"%d %d\"%(dp[countDp-1][0],dp[countDp-1][1]))\n",
    "        count += 1\n",
    "        while(count<n):\n",
    "            j = count\n",
    "            while(j+1<n and nums[j+1]==nums[j]):\n",
    "                j += 1\n",
    "            if(nums[count]==nums[count-1]+1):\n",
    "                dp[countDp][0] = max(dp[countDp-1][0],dp[countDp-1][1])\n",
    "                dp[countDp][1] = dp[countDp-1][0] + nums[count]*(j-count+1)\n",
    "            else :\n",
    "                dp[countDp][0] = max(dp[countDp-1][0],dp[countDp-1][1])\n",
    "                dp[countDp][1] = max(dp[countDp-1][0],dp[countDp-1][1])+nums[count]*(j-count+1)\n",
    "            countDp += 1\n",
    "            print(\"%d %d\"%(dp[countDp-1][0],dp[countDp-1][1]))\n",
    "            count = j+1\n",
    "        return max(dp[countDp-1][0],dp[countDp-1][1])\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
